#include<stdio.h>
#include<conio.h>
#define num 40000
int a[num],trace[num],h[num],l[num],i,j,n,k,max,temp,s;
void input(){
    FILE *fp=fopen("DAYCON.INP","r");
    fscanf(fp,"%d",&n);
    for(i=1;i<=n;i++)
        fscanf(fp,"%d",&a[i]);
    fclose(fp);
}
void process(){
    long left,right,center;
    k=1;
    h[1]=a[1];
    l[1]=1;
    trace[1]=0;
    for(i=2;i<=n;i++){
        left=1;right=k+1;
        while(right-left>1){
            center=(left+right)/2;
            if(h[center]>a[i])right=center;
            else left=center;
        }
        if(left==k)k++;
        trace[i]=l[left];
        left++;
        h[left]=a[i];
        l[left]=i;
    }
}
void output1(){
    printf("%d in %d \n",k,max);
    k=l[k];
    while(k>0){
        printf("%d ",a[k]);
        k=trace[k];
    }
}
void output(){
    printf("%d in %d \n",l[k],l[max]);
    for(i=1;i<=n;i++)printf("(%2d : %2d is %2d)\n",i,trace[i],a[i]);
}
int main(){
    input();
    process();
    output();
    getch();
    return 0;
}
